package Day_016_T264;

/**给你一个整数 n ，请你找出并返回第 n 个 丑数 。

 丑数 就是只包含质因数2、3 和/或5的正整数。



 示例 1：

 输入：n = 10
 输出：12
 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
 示例 2：

 输入：n = 1
 输出：1
 解释：1 通常被视为丑数。


 提示：

 1 <= n <= 1690

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/ugly-number-ii
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 **/
public class T264 {
    public int nthUglyNumber(int n) {

        //后面的丑数都是有前面的丑数 生成

        int[] nums = new int[n+1];

        nums[0] = 1;
        if (n==1){

            return 1;
        }
// pi 的作用是 记录 2 ,3 ,5 是否跟nums[pi] 相乘过
        int p2 = 0;
        int p3 = 0;
        int p5 = 0;


        for (int i = 1; i<=n; i++) {
            int min = Math.min(nums[p2] * 2, (Math.min(nums[p3] * 3, nums[p5] * 5)));
            System.out.println(min);
            nums[i] = min;

            if(min==nums[p2]*2) p2++;
            if (min==nums[p3]*3) p3++;
            if (min==nums[p5]*5) p5++;

        }

        return nums[n-1];

    }

    public static void main(String[] args) {
        T264 t264 = new T264();
        int i = t264.nthUglyNumber(5);
        System.out.println("----"+i);
    }

}
